// 2025/3/22
// https://leetcode.cn/problems/largest-rectangle-in-histogram/description/?envType=study-plan-v2&envId=top-100-liked
// 柱状图中最大的矩形

class Solution {
    public:
        int largestRectangleArea(vector<int>& heights) {
            int n = heights.size();
            vector<int> leftV(n), rightV(n);
    
            stack<int> leftSt;
            for(int i = 0; i < n; i++)
            {
                while(!leftSt.empty() && heights[i] <= heights[leftSt.top()])
                {
                    leftSt.pop();
                }
                leftV[i] = leftSt.empty() ? -1 : leftSt.top();
                leftSt.push(i);
            }
    
            stack<int> rightSt;
            for(int j = n - 1; j >= 0; j--)
            {
                while(!rightSt.empty() && heights[j] <= heights[rightSt.top()])
                {
                    rightSt.pop();
                }
                rightV[j] = rightSt.empty() ? n : rightSt.top();
                rightSt.push(j);
            }
    
            int ans = 0;
            for(int k = 0; k < n; k++)
            {
                ans = max(ans, heights[k] * (rightV[k] - leftV[k] - 1));
            }
            return ans;
        }
    };

// 优化一轮循环
class Solution {
    public:
        int largestRectangleArea(vector<int>& heights) {
            int n = heights.size();
            vector<int> leftV(n), rightV(n, n);
    
            stack<int> leftSt;
            for(int i = 0; i < n; i++)
            {
                while(!leftSt.empty() && heights[i] <= heights[leftSt.top()])
                {
                    rightV[leftSt.top()] = i;
                    leftSt.pop();
                }
                leftV[i] = leftSt.empty() ? -1 : leftSt.top();
                leftSt.push(i);
            }
    
            int ans = 0;
            for(int k = 0; k < n; k++)
            {
                ans = max(ans, heights[k] * (rightV[k] - leftV[k] - 1));
            }
            return ans;
        }
    };